Recent image data has a large data amount, and compression coding is effectively used to reduce the data amount. A general image encoding apparatus will be described below. As shown in FIG. 5, an image captured by an image sensing device or the like is divided into rectangular tiles each having a desired size. Each tile is further divided into two-dimensional MBs (macroblocks). Each MB data undergoes orthogonal transformation and is thus converted from color space data to transform coefficients in the frequency space. Quantization processing is also performed for the transform coefficients as needed. If the data pattern of the image extends across a plurality of blocks, intra-frame prediction is performed to obtain the quantized transform coefficients in accordance with the frequency bands, thereby further decreasing the strength of the transform coefficients. The two-dimensional transform coefficients that have undergone quantization and intra-frame prediction are sorted into one-dimensional data by continuously placing significant coefficients first and zero runs next. The sorted one-dimensional data is entropy-coded to generate a code stream. The code stream generated in the above-described way is reconstructed into an image in accordance with a reverse processing procedure.
Run-length encoding in JPEG or the like, one-dimensionally scans two-dimensional transform coefficients in accordance with a predetermined pattern, thereby encoding the lengths of continuous runs. FIG. 3A shows an example of the scan pattern. Scanning is performed in the illustrated numerical order. This is called a “zigzag” pattern because the numerical order indicates a zigzag route. However, a predetermined pattern such as the “zigzag” pattern does not necessarily contribute to the encoding efficiency due to the following three reasons. First, if conversion is performed across a plurality of blocks to suppress block distortion, the edge is enhanced, resulting in a larger transform coefficient variance and a higher transform coefficient strength. In this case, the strength of a low-frequency transform coefficient (the transform coefficient at the lower right corner of a block) does not always decrease. For this reason, the scan order for scanning transform coefficients from the upper left to the lower right of a block is not necessarily optimum. Second, when the pixels in a block have a dependence in the horizontal or vertical direction, the frequency bands of transform coefficients tend to localize in accordance with the dependence. In this case, a scan order that changes in the horizontal or vertical direction, as shown in FIG. 3B or 3C, is suitable. Third, if a texture exists across blocks, transform coefficients localize between the blocks in the same tendency. In this case, coefficient prediction is performed for the quantized transform coefficients, thereby suppressing the coefficient strength. The localization of the frequency bands of the transform coefficients changes depending on the prediction method. Hence, a scan pattern complying with the prediction method is necessary. For the above-described reasons, it is preferable to select an optimum scan order suitable for an input image and an encoding scheme (e.g., Japanese Patent Laid-Open No. 2004-032788).
A recent encoding scheme represented by JPEG-XR that is being standardized further divides each MB into blocks so as to change the quantized values or intra-frame prediction method in each block. In this scheme, the scan order is changed for each block (e.g., Japanese Patent Laid-Open Nos. 2006-191628 and 07-050836). For example, according to the scan order deciding method described in Japanese Patent Laid-Open No. 2006-191628, an MB including 16×16 pixels is divided into blocks each including 4×4 pixels, as shown in FIG. 4. Scan conversion of the blocks is performed in the order of A to P in FIG. 4. According to this method, the scan conversion result of the block A is analyzed, that is, the coefficients are analyzed in the order after sorting, thereby determining the scan order of the next block B. Similarly, the scan conversion result of the block B is analyzed, that is, the coefficients are analyzed in the order after sorting, thereby deciding the scan order of the next block C. In the same way, depending on the scan conversion result of the current process target block, the scan order of the next block is decided. The scan order deciding method will be described in more detail with reference to FIG. 6. First, in step S801, one transform coefficient C[n] (n≧0) is acquired in the one-dimensional order from a block that has undergone scan conversion. Next, in step S802, it is determined whether the coefficient C[n] acquired in step S801 is a run (zero). If the transform coefficient C[n] is a run, the process advances to determination in step S804. On the other hand, if the transform coefficient C[n] is a significant coefficient (nonzero), the process in step S803 is executed. There is a statistical information table ScanTotals which statistically obtains positions where significant coefficients are generated in a 4×4 block (e.g., FIG. 7A). FIG. 7A shows statistical information table values corresponding to the positions (e.g., FIG. 7B) in the 4×4 pixel block corresponding to the scan order, for the descriptive convenience. Note that the initial values of the statistical information ScanTotals are set as follows in some cases.
{t*N, t*(N−1), t*(N−2), . . . , t}
In general, a small integer (2 or 4) is selected as t. The value t may be decided by a quantization parameter used in quantization. Resetting the statistical information at a predetermined period enables to fix the maximum bit length of the elements of the statistical information. There also exists a table ScanOrder representing the correspondence between the scan order and the positions of coefficients in a 4×4 pixel block. The initial order of the coefficient positions ScanOrder corresponding to the scan order is preferably decided causally between an image encoding processing apparatus and an image decoding processing apparatus. For example, when coefficient prediction has been done in the horizontal direction, the scan order is initialized to the order of preferentially scanning in the horizontal direction (FIG. 3B). On the other hand, when coefficient prediction has been performed in the vertical direction, the scan order is initialized to the order of preferentially scanning in the vertical direction (FIG. 3C). Note that the scan order in the horizontal direction may also be used as the initial scan order of a block that does not exhibit any specific directivity. Each symbol from a to o in FIG. 4 indicates correspondence with a coefficient position in a given 4×4 pixel block shown in FIG. 4. Referring to FIG. 7B, the scan order table ScanOrder in the initialized status shown in FIG. 3B is represented by a to o in FIG. 4. For a significant coefficient, the appearance frequency value of the corresponding element in the statistical information table ScanTotals is incremented (increased) in step S803. In step S804, the two pieces of statistical information ScanTotals[n] and ScanTotals[n−1] are compared. ScanTotals[n]>ScanTotals[n−1] means that the number of times of significant coefficient generation is larger at the position of the transform coefficient C[n] than at the position of a transform coefficient C[n−1]. Hence, in step S805, conversion processing is performed for the coefficient position ScanOrder corresponding to the scan order as shown in FIGS. 7A and 7B and ScanTotals corresponding to it. If the statistical information ScanTotals[n]≦ScanTotals[n−1] in step S804, the scan order change processing is not executed.
The conversion processing in step S805 will be described in detail. In the conversion processing, to replace the coefficient positions ScanOrder[n] and ScanOrder[n−1] with each other, for example, the following calculations are performed.Temp=ScanOrder[n−1]ScanOrder[n−1]=ScanOrder[n]ScanOrder[n]=Temp
To replace the statistical information ScanTotals[n] and ScanTotals[n−1] with each other, for example, the following calculations are performed.Temp=ScanTotals[n−1]ScanTotals[n−1]=ScanTotals[n]ScanTotals[n]=Temp
Upon determining in step S806 that transform coefficient acquisition in the block for scan order decision has not ended yet, the process advances to step S807 to prepare for acquisition of the next coefficient. If all coefficients in the block have been acquired, the scan order decision procedure ends.
As described above, the coefficient position ScanOrder[n−1] corresponding to the scan order n−1 is causally decided using the statistical information ScanTotals[n] and ScanTotals[n−1] corresponding to the scan orders n and n−1. This allows an optimum scan order stepwise to be decided. In addition, since the scan order can causally be decided, the encoding apparatus need not add, to the code stream, information to explicitly notify the decoding apparatus of the scan order.
As described above, in the scan order deciding method of deciding the scan order of a block based on the status of the preceding block, the scan order can change for each block. In such scan conversion processing, it is difficult to execute scan conversion of a plurality of blocks, and so the processing cannot be sufficiently speeded up.